package com.itheima.algorithm.backtracking;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * N皇后 - 回溯
 */
public class NQueenLeetcode51 {

    public static void main(String[] args) {
        NQueenLeetcode51 leetcode51 = new NQueenLeetcode51();
        List<List<String>> result = leetcode51.solveNQueens(4);
        System.out.println(result.toString());
    }

    public List<List<String>> solveNQueens(int n) {
        List<List<String>> result = new ArrayList<>();
        boolean[] ca = new boolean[n]; // 记录列冲突
        // true false false false
        boolean[] cb = new boolean[2 * n - 1]; // 左斜线冲突
        // i+j
        boolean[] cc = new boolean[2 * n - 1]; // 右斜线冲突
        // n-1-(i-j)
        char[][] table = new char[n][n]; // '.''Q'
        for (char[] t : table) {
            Arrays.fill(t, '.');
        }

        /*for (char[] t : table) {
            System.out.println(new String(t));
        }*/
        // true false false false
        dfs(0, n, table, ca, cb, cc, result);
        return result;
    }

    static void dfs(int i, int n, char[][] table,
                    boolean[] ca,
                    boolean[] cb,
                    boolean[] cc,
                    List<List<String>> result) {
        if (i == n) { // 找到解
            List<String> list = new ArrayList<>();
            result.add(list);
            for (char[] t : table) {
                list.add(new String(t));
            }
            return;
        }
        for (int j = 0; j < n; j++) {
            if (ca[j] || cb[i + j] || cc[n - 1 - (i - j)]) {
                continue;
            }
            table[i][j] = 'Q';
            ca[j] = cb[i + j] = cc[n - 1 - (i - j)] = true;
            dfs(i + 1, n, table, ca, cb, cc, result);
            table[i][j] = '.';
            ca[j] = cb[i + j] = cc[n - 1 - (i - j)] = false;
        }
    }
}
